//验证二叉搜索树


function isValidBST(root) {
    let pre = null;
    function inorder(node){
        if(!node) return true;
        if(!inorder(node.left)) return false;
        if(pre && node.val <= pre.val) return false;
        pre = node;
        return inorder(node.right);
    }
    return inorder(root);
}

// 构造二叉树节点
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

// 测试用例1: 有效的二叉搜索树
//       5
//      / \
//     3   8
//    / \ / \
//   2  4 7  9
const root1 = new TreeNode(5);
root1.left = new TreeNode(3);
root1.right = new TreeNode(8);
root1.left.left = new TreeNode(2);
root1.left.right = new TreeNode(4);
root1.right.left = new TreeNode(7);
root1.right.right = new TreeNode(9);

console.log("测试用例1 - 有效的BST:", isValidBST(root1)); // 应该返回 true

// 测试用例2: 无效的二叉搜索树
//       5
//      / \
//     3   8
//    / \ / \
//   2  6 7  9  (6 > 5，违反BST性质)
const root2 = new TreeNode(5);
root2.left = new TreeNode(3);
root2.right = new TreeNode(8);
root2.left.left = new TreeNode(2);
root2.left.right = new TreeNode(6); // 这个节点导致不是有效的BST
root2.right.left = new TreeNode(7);
root2.right.right = new TreeNode(9);

console.log("测试用例2 - 无效的BST:", isValidBST(root2)); // 应该返回 false

// 测试用例3: 空树
const root3 = null;
console.log("测试用例3 - 空树:", isValidBST(root3)); // 应该返回 true

// 测试用例4: 单个节点
const root4 = new TreeNode(1);
console.log("测试用例4 - 单个节点:", isValidBST(root4)); // 应该返回 true

// 测试用例5: 所有节点值相等
//   2
//  / \
// 2   2
const root5 = new TreeNode(2);
root5.left = new TreeNode(2);
root5.right = new TreeNode(2);
console.log("测试用例5 - 相等节点值:", isValidBST(root5)); // 应该返回 false

// 测试用例6: 只有右子树的BST
// 1
//  \
//   2
//    \
//     3
const root6 = new TreeNode(1);
root6.right = new TreeNode(2);
root6.right.right = new TreeNode(3);
console.log("测试用例6 - 只有右子树:", isValidBST(root6)); // 应该返回 true
